package main.Q401_500;

import java.util.Arrays;

public class Q471_480 {
    public static void main(String[] args) {
        System.out.println("Question471：");
        System.out.println("Question472：");
        System.out.println("Question473：火柴拼正方形");
        System.out.println("Question474：");
        System.out.println("Question475：");
        System.out.println("Question476：数字的补数");
        System.out.println("Question477：汉明距离总和");
        System.out.println("Question478：");
        System.out.println("Question479：");
        System.out.println("Question480：");
    }
}

class Question473{
    public boolean makesquare(int[] matchsticks) {
        int totalLen = Arrays.stream(matchsticks).sum();
        if (totalLen % 4 != 0) return false;
        int len = totalLen / 4, n = matchsticks.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int s = 1; s < (1 << n); s++) {
            for (int k = 0; k < n; k++) {
                if ((s & (1 << k)) == 0) continue;
                int s1 = s & ~(1 << k);
                if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                    dp[s] = (dp[s1] + matchsticks[k]) % len;
                    break;
                }
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
}

class Question476{
    public static int findComplement(int num) {
        char[] bit=Integer.toBinaryString(num).toCharArray();
        StringBuffer stringBuffer=new StringBuffer();
        for (int i=0;i<bit.length;i++){
            if (bit[i]=='0') stringBuffer.append('1');
            else stringBuffer.append('0');
        }
        return Integer.parseInt(stringBuffer.toString(),2);
    }
}

class Question477 {
    public int totalHammingDistance(int[] nums) {
        int result = 0, n = nums.length;
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int val : nums) {
                c += (val >> i) & 1;
            }
            result += c * (n - c);
        }
        return result;
    }
}